package demo;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树先序遍历
 */
public class Solution44 {
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				list.add(node.val);
				stack.push(node);
				node = node.left;

			}
			if (!stack.isEmpty()) {
				node = stack.pop();
				node = node.right;
			}
		}
		return list;
	}
}
